package kyssion.leetcode.num201_250;

public class code211_添加与搜索单词数据结构设计 {

    public static void main(String[] args) {
        new code211_添加与搜索单词数据结构设计().test();
    }

    public void test() {
        WordDictionary2 dictionary = new WordDictionary2();
        dictionary.addWord("bad");
        dictionary.addWord("bada");
        System.out.println(dictionary.search("bad"));

    }

    class WordDictionary2 {
        class TrieNode {
            public TrieNode[] children = new TrieNode[26];
            public boolean isEnd;
        }

        private TrieNode root = new TrieNode();

        /**
         * Initialize your data structure here.
         */
        public WordDictionary2() {
        }

        /**
         * Adds a word into the data structure.
         */
        public void addWord(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                if (node.children[c - 'a'] == null) {
                    node.children[c - 'a'] = new TrieNode();
                }
                node = node.children[c - 'a'];
            }
            node.isEnd = true;
        }

        /**
         * Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter.
         */
        public boolean search(String word) {
            return match(word.toCharArray(), 0, root);
        }

        private boolean match(char[] chs, int k, TrieNode node) {

            //之前的写法会考虑这里是-1 的情况下的问题,但是实际上并不需要考虑这里
            //因为 递归的逻辑是判断这一层是否有带确定的值,如果有将待确定的值传递到下一层,并且继续重复这个逻辑
            //通过这个过程可以发现如果是在边界上的时候,传入的node就是最后一位所以只要对最后一位进行判断即可了
            if (k == chs.length) {
                return node.isEnd;
            }
            if (chs[k] != '.') {
                return node.children[chs[k] - 'a'] != null && match(chs, k + 1, node.children[chs[k] - 'a']);
            } else {
                for (int i = 0; i < 26; i++) {
                    if (node.children[i] != null) {
                        if (match(chs, k + 1, node.children[i])) {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }
}
